#include <iostream>
#include <vector>
#include <cmath> // 用于abs
using namespace std;

// 检查皇后k放置在x[k]列是否发生冲突
// 返回true表示产生冲突，不能放置
// 返回false表示可以放置在该位置
bool checkPlace(int k, const vector<int>& x) {
    for (int i = 0; i < k; i++) {
        if (x[i] == x[k] || abs(i - k) == abs(x[i] - x[k])) {
            return true;
        }
    }
    return false;
}

// 回溯法求解n皇后问题
int queen(int n) {
    // x[i]表示第i行放置皇后的列下标，-1表示未放置
    vector<int> x(n, -1);
    int k = 0, count = 0;

    // 循环模拟递归，摆放皇后k
    while (k >= 0) {
        x[k]++;
        while (x[k] < n && checkPlace(k, x)) {
            x[k]++;
        }
        if (x[k] < n && k == n - 1) {
            // 打印当前解
            for (int j = 0; j < n; j++) {
                cout << x[j] + 1 << "  ";
            }
            cout << endl;
            ++count;
        }
        if (x[k] < n && k < n - 1) {
            k = k + 1;
        } else {
            x[k--] = -1;
        }
    }
    // 最后返回总共有多少组解
    return count;
}

int main() {
    int ans = queen(4);
    cout << "共有 " << ans << " 个解!" << endl;
    return 0;
}